import functools
from typing import List


class Solution:
    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:
        s1, s2 = len(workers), len(bikes)

        distances = [[0] * s2 for _ in range(s1)]

        for i in range(s1):
            for j in range(s2):
                distances[i][j] = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1])

        @functools.lru_cache(None)
        def dfs(ii, stat):
            if ii == s1:
                return 0
            else:
                res = float("inf")
                for jj in range(s2):
                    if not stat & (1 << jj):
                        res = min(res, res, dfs(ii + 1, stat | (1 << jj)) + distances[ii][jj])
                return res

        return dfs(0, 0)


if __name__ == "__main__":
    print(Solution().assignBikes(workers=[[0, 0], [2, 1]], bikes=[[1, 2], [3, 3]]))  # 6
    print(Solution().assignBikes(workers=[[0, 0], [1, 1], [2, 0]], bikes=[[1, 0], [2, 2], [2, 1]]))  # 4
